As Information technology advances more and more sophisticated, enterprises and individuals need to process much larger amount of data. Also, resources for managing this large amount data have increased very significantly. However, it is not easy for all members of information technology society to bear necessary cost to manage this large amount of information. Accordingly, external database services are more and more utilized to store information.
However, the external database services have increasing problems of personal information leakage. Therefore, it is important to provide a solution to solve this problem.
Currently, a most attracting solution for this problem is to encrypt every data to be stored in database. An encryption system, which has been a basis of information protection for longtime, ensures the security of encrypted ciphertext.
Meanwhile, a database system provides not only a simple storage of data but also an application environment to search and utilize data in the database. However, since an encrypted data hinders the database system from obtaining any kind of information from itself, the solution encrypting all data to be stored fundamentally blocks application services of database system. To solve this drawback, a lot of studies, from a basic study on a searching method for encrypted database to an advanced study on processing method of performing a desired operation on the encrypted data without decryption, are underway over various areas.
Among various studies as described above, the order-preserving encryption scheme is attracting big attention. This is because many application services that database can provide with are based on order information of data. Efficient searching, size comparing, and range search, and the like are basic application service that can be provided. However, it is contradictory to hide information of a plaintext enough and at the same time open an order-information of the plaintext. Therefore, it is very difficult problem to make an efficient and safe order-preserving encryption scheme, and there is no concrete solution to this problem.
More specifically, in ordinary encryption methods, a plaintext space and a ciphertext space may be constructed identically, but, it is difficult to construct an encryption if selecting the plaintext and ciphertext in the same space in the order-preserving encryption method, since there is none other than a homologous function in this case.
Moreover, ordinary encryption methods generally assume CPA (chosen plaintext attack) or CCA (chosen ciphertext attack) as an attacking scheme to analyze security of the methods, but the order-preserving encryption method does not allow those CPA or CCA attacking schemes because an attacker can perform decryption substantially using those CPA or CCA attacking schemes. For the same reason, it is known to be difficult to construct an open key type order-preserving encryption method.
As described above, the order-preserving encryption is an unsolved problem.
Earlier studies on the order-preserving encryption mainly focused on a scheme in which given plaintext is random-numbered into a cipertext space of larger size.
A systematic study on the order-preserving encryption was done by Agrawal et al. in 2004 for the first time. Agrawal et al. assume a distribution of plaintext as information which is only known to a user, and build an encryption function in order not to open the distribution of the given plaintext after encryption by using the distribution of the given plaintext. They also proposed systematic security and said that in their proposal if an attacker can not infer a distribution of plaintext before an encryption from a given set of ciphertext, the encryption can be defined a secure order-preserving encryption.
However, since above scheme's security is depending on an assumption that user knows all the information on the data to be encrypted before starting encryption, the scheme is far from a practical encryption function.
Later, Boldyreva et al performed a study to apply provable security to the order-preserving function. They proposed a new definition of the provable security for the order-preserving encryption method by using a security definition of a pseudo-random number generating function, beyond a traditional provable security approach for an encryption function. Security of a pseudo-random number function is shown by a fact that a pseudo-random number array generated by a pseudo-random number function can not be distinguished with a real random number array. Similarly, Boldyreva et al defined that an arbitrary order-preserving encryption function can not be distinguished with another arbitrary one.
However, this kind approach is regarded not to satisfy a basic security that an encryption function needs to have. In other words, the basic security that the encryption function needs to have is to ensure that an attacker can not infer information of plaintext from ciphertext.
According to the scheme proposed by the Boldyreva, since an order-preserving function is arbitrarily selected from a set of all possible order-preserving functions, the distribution of entire selected order-preserving functions is same as that of the set of all possible order-preserving functions. That is, an attacker can calculate a distribution of plaintext candidates, into which each ciphertext may decrypted, from the set of all possible order-preserving functions. Here, it can be found that a probability that most of ciphertexts may match with a certain plaintext is very high. The larger the number of plaintexts and ciphertexts is, the more often this phenomenon becomes. Also, more serious problem may occur if admitting a little amount of error.
As discussed above, even though the order-preserving encryption method is a very attention-attracting technology in encryption technology area, a reliabe solution has not been introduced yet.